package com.example.lettcode._202410._20241016;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/*
71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下：
一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。

 示例 1：
输入：path = "/home/"
输出："/home"
解释：
应删除尾随斜杠。

示例 2：
输入：path = "/home//foo/"
输出："/home/foo"
解释：
多个连续的斜杠被单个斜杠替换。

示例 3：
输入：path = "/home/user/Documents/../Pictures"
输出："/home/user/Pictures"
解释：
两个点 ".." 表示上一级目录（父目录）。

示例 4：
输入：path = "/../"
输出："/"
解释：
不可能从根目录上升一级目录。

示例 5：
输入：path = "/.../a/../b/c/../d/./"
输出："/.../b/d"
解释：
"..." 在这个问题中是一个合法的目录名。


创建一个队列

将路径用 '/' 进行分割开

遍历入队
如果有'..' 则判断队列是否为空，
	为空，则返回'/', 不
	为空，则队列中最后一个出队，
	为'.'，则不入队，不做处理
 */
public class _1_Jian_hua_lu_jing {

    public static void main(String[] args) {
        // String path = "/a/../../b/../c//.//";
        // String path = "/home//foo/";
        String path = "/home/";
        System.out.println(simplifyPath(path));

        String builder = "/home/";
        System.out.println(builder.substring(0, builder.length() - 1));
    }

    public static String simplifyPath2(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<>(); // 这个还不能用单纯的栈呢，得用双端队列
        for (String name : names) {
            if ("..".equals(name)) { // 对于两个点，需要将目录切换到上一级
                if (!stack.isEmpty()) { // 所以只要栈不为空【因为不管如何取上一级，到/根目录也就停了】，就弹出栈顶元素
                    stack.pollLast(); // 弹出栈顶元素
                }
            } else if (name.length() > 0 && !".".equals(name)) { // 不是空字符串或者一个点
                stack.offerLast(name); // 否则就是目录名，直接入栈
            }
        }
        // 全部对last进行poll或者offer就是栈的形式，想想一下
        StringBuilder builder = new StringBuilder();
        if (stack.isEmpty()) {
            builder.append('/');
        } else {
            while (!stack.isEmpty()) {
                builder.append('/').append(stack.pollFirst()); // 先进去的先出来，这样结果才对
            }
        }
        return builder.toString();
    }

    public static String simplifyPath(String path) {
        if (path == null || path.charAt(0) != '/') {
            return "/";
        }

        Deque<String> linkedList = new LinkedList<>();
        linkedList.push("1");
        String[] split = path.split("/");
        for (int i = 0; i < split.length; i++) {
            String s = split[i];
            if ("..".equals(s)){
                if (!linkedList.isEmpty()) {
                    linkedList.removeLast();
                }
            } else if (s.length() > 0 && !".".equals(s)) {
                linkedList.addLast(s);
            }
        }
        StringBuilder builder = new StringBuilder("/");
        if (!linkedList.isEmpty()) {
            linkedList.stream().forEach(e -> builder.append(e).append("/"));
            return builder.substring(0, builder.length()-1);
        } else {
            return builder.toString();
        }
    }
}
